package medium.array;

/**
 * <a href="https://leetcode-cn.com/problems/peaks-and-valleys-lcci">面试题 10.11. 峰与谷</a>
 * 在一个整数数组中，“峰”是大于或等于相邻整数的元素，相应地，“谷”是小于或等于相邻整数的元素。例如，在数组{5, 8, 4, 2, 3, 4, 6}中，{8, 6}是峰， {5, 2}是谷。现在给定一个整数数组，将该数组按峰与谷的交替顺序排序。
 * 示例:
 *   输入: [5, 3, 1, 2, 3]
 *   输出: [5, 1, 3, 2, 3]
 * 提示：
 *   nums.length <= 10000
 * 解题思路：
 *   1.利用boolean来标志当前需要峰->谷还是谷->峰，初始化为true表示峰->谷
 *   2.从第二个元素开始遍历数组，每次与前一个元素作比较
 *   3.若前一个元素小于当前元素，且标志为峰->谷，则需要对这两个元素进行交换
 *   4.每次循环都要对标志取反，表示峰谷顺序变换
 *   5.遍历完后，即完成了峰谷交替
 * @author 刘学松
 * @date 2021-04-11 22:06
 */
public class 峰与谷 {
    public void wiggleSort(int[] nums) {
        boolean flag = true;
        for (int i=1; i<nums.length; i++) {
            if (nums[i-1] < nums[i] == flag) {
                int temp = nums[i-1];
                nums[i-1] = nums[i];
                nums[i] = temp;
            }
            flag = !flag;
        }
    }
}
